如何实现全同态加密的电路隐私保护？
问题起源
考虑这样的全同态加密计算应用：用户A拥有私密的明文输入 ，用户B拥有私密的计算函数 (假定该函数可以表示成布尔电路)。用户A希望能在自己的私有 上做一次函数运算 但是不泄露 ; 用户B希望自己的函数 不被泄露。
这里，我们不希望需要计算的函数 被别人得知。然而，在目前的全同态加密方案中，计算函数 和密文的噪声分量有密切关系。简单地说， 的计算深度越深，密文噪声也越大，因此敌手可能通过分析密文噪声获取 ，因此全同态加密的电路隐私(circuit privacy)问题就是寻找有效的方法使得经过同态运算后的密文噪声和被计算函数 无关。
笔者列举一个具体的全同态加密计算应用例子说明电路隐私问题的重要性。在使用全同态加密设计隐私集合求交协议时[1], sender需要同态地计算一个多项式函数 ，这里 是sender集合 中的任意一个元素, 是一个随机数。如果电路隐私的性质不能保证，那么 receiver对 解密，并观察解密结果中可以察觉到其中的噪声分量和 存在关联，进而泄露了 。
下面，笔者总结目前学界已知的电路隐私技术如下(参考YouTube视频[2])。
Noise flooding
Smudging lemma[3]指出若一个整数 满足 ,那么 上的均匀分布和 上的均匀分布是（统计）不可区分的。据此，假定FHE密文 的噪声分量 在 之间，那么只需要对原FHE密文做一次同态加法, 即 , 且 的噪声分量在 即可。
Noise flooding最大的弊端是需要选取非常大的FHE参数进而造成更大的密文长度和更慢的运算速度。这是因为原先的FHE只需要容纳的噪声上限为 , 现在需要容纳幅值为 的噪声，噪声容纳上限呈指数型增长。为了解密的正确性，需要选取巨大的FHE参数。
Washing machine
基本方法
[4] 提出组合bootstrapping和noise flooding来达成密文噪声分量不可区分的目的，即：
注意这里的noise flooding是小“剂量”的：中的噪声分量满足
, 这样使得 之间的统计距离(statistical distance)
; bootstrap不会增大统计距离(衣服 data processing inequality)即
，但是会降低 噪声分量的幅值以保证解密得正确性。重复上述步骤 次
，最终使得
，即 的概率分布不可区分。
上述方法又称之为soak-spin repeat strategy， 是'soak', bootstrap是'spin'，也就是洗衣机(washing machine)的工作原理。
以FHEW[5]为例
现在以第三代FHE方案FHEW[6]为例，具体说明如何使用soak-spin repeat strategy, 如下图所示：
我们在FHEW bootstrapping的中间步骤插入 , 即
这里
所以, Rerand之后，统计距离降低为 。重复soak-spin repeat strategy 次，最终使得统计距离可忽略。
参考文献
[1]https://zhuanlan.zhihu.com/p/589081394
[2]https://www.youtube.com/watch?v=_tg0kmI5hkE&t=14s
[3]Asharov, Gilad, et al. "Multiparty computation with low communication, computation and interaction via threshold FHE." Advances in Cryptology–EUROCRYPT 2012: 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings 31. Springer Berlin Heidelberg, 2012.
[4]Ducas, Léo, and Damien Stehlé. "Sanitization of FHE ciphertexts." Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I 35. Springer Berlin Heidelberg, 2016.
[5]Ducas, Léo, and Daniele Micciancio. "FHEW: bootstrapping homomorphic encryption in less than a second." Advances in Cryptology--EUROCRYPT 2015: 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I 34. Springer Berlin Heidelberg, 2015.
[6]https://zhuanlan.zhihu.com/p/589934167
对全同态加密知识感兴趣的同学，可以点击全同态加密知识体系整理(上)、全同态加密知识体系整理(下）进行学习。
本文作者：hujwei
知乎链接：https://zhuanlan.zhihu.com/p/597950821
往期推荐
1.多方安全计算知识点整理——比特承诺
2.CVPR 2023 | 用「影子」模拟攻击者行为，提升系统安全性论文分享 | Le Mans: Dynamic and Fluid MPC for Dishonest Majority4.多方安全计算知识点整理——秘密分享